package com.mlh.sort;

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
		int[] arr = {53, 17, 78, 9, 45, 65, 87, 32, 345, 7, 67, 1, 1, 1, 1, 1, 1, 1, 45, 6, 7, 8, 5, 3, -3};
		method1(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}

	//快排思想同荷兰国旗问题
	public static void method1(int[]arr,int begin,int end){
		if(begin>=end){
			return;
		}
		int val=arr[end];//选定划分值
		int temp;//用于元素交换
		int left=begin,right=end;//定义左边界和右边界 边界指向的前一位才是符合定义的值 即左边界前一位到尽头都是小于val 有边界如此
		int pointer=begin;//指针指向未做比较的元素
		while (pointer<=right){
			if(arr[pointer]<val){
				temp=arr[pointer];
				arr[pointer]=arr[left];
				arr[left]=temp;
				left++;
				pointer++;//这边需要++是最容易忽视的 也是很关键的
				//一种情况左边界和pointer指向同一元素，则比较完要++
				//另一种情况是左边界和pointer指向不同元素，因此交换过来的元素一定是等于val，因此不需要在做比较直接++
			}else if(arr[pointer]>val){
				temp=arr[pointer];
				arr[pointer]=arr[right];
				arr[right]=temp;
				right--;
			}else{
				pointer++;
			}
		}
		method1(arr,begin,left-1);
		method1(arr,right+1,end);
	}
}
